package leetcode.editor.cn;

import algs4.In;

import java.util.*;

/**
 * Copyright (C) 2023 思创数码科技股份有限公司
 * <p/>
 * 版权所有
 * <p/>
 * 类名　　  : p556
 * 功能概要  :
 *
 * @author yangwk
 * @date 2024/9/14 15:50
 */
public class P556 {
    public static void main(String[] args) {
        System.out.println(new P556().nextGreaterElement(122));


    }

    public int nextGreaterElement(int n) {
        List<Integer> list = new ArrayList<>();
        int num = n;
        while (num != 0) {
            int val = num % 10;
            list.add(val);
            num /= 10;
        }
        visited = new boolean[list.size()];
        List<Integer> combine = combine(list, 0, 0);
        Long minGreatest = Long.MAX_VALUE;
        for (Integer ele : combine) {
            if (ele > n && ele < minGreatest) {
                minGreatest = Long.valueOf(ele.intValue());
            }
        }
        return minGreatest.intValue();
    }

    boolean[] visited;

    public List<Integer> combine(List<Integer> list, int index, int num) {
        List<Integer> result = new ArrayList<>();
        if (index == list.size()) {
            result.add(num);
            return result;
        }
        Set<Integer> dumpSet = new HashSet<>();
        for (int i = 0; i < list.size(); i++) {
            if (visited[i]) {
                continue;
            }
            if (dumpSet.contains(list.get(i))) {
                continue;
            }
            long val = num * 10 + list.get(i);
            if (val > Integer.MAX_VALUE) {
                continue;
            }
            visited[i] = true;
            dumpSet.add(list.get(i));
            result.addAll(combine(list, index + 1, (int) val));
            visited[i] = false;
        }
        return result;
    }
}
